package day06;

/**
 * 2598. 找出缺失的最小整数
 * 给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。
 *
 * 在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。
 *
 * 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。
 * 数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。
 *
 * 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。
 * 返回在执行上述操作 任意次 后，nums 的最大 MEX 。
 */
public class No2598 {
    public int findSmallestInteger(int[] nums, int value) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        // 统计每个余数出现的次数
        int[] remainderArray = new int[value];
        for (int num : nums) {
            int remainder = getRemainder(num, value);
            remainderArray[remainder]++;
        }
        // 找到出现次数最少的余数及其位置
        int minLoc = 0;
        int minMultiple = remainderArray[0];
        for(int i=1; i<value; i++){
            if(remainderArray[i] < minMultiple){
                minMultiple = remainderArray[i];
                minLoc = i;
            }
        }
        // 根据出现次数最少的余数计算结果
        return minLoc + minMultiple * value;
    }

    /**
     * 计算a除以b的非负余数
     * @param a 被除数
     * @param b 除数
     * @return a除以b的非负余数
     */
    public int getRemainder(int a, int b){
        int multiple = a / b;
        int remainder = a - multiple*b;
        return remainder + (remainder<0 ? b : 0);
    }
}
